package cn.zifangsky.linkedlist.questions;

import org.junit.Test;

import cn.zifangsky.linkedlist.SinglyNode;

/**
 * 单链表求最大值
 * @author zifangsky
 *
 */
public class Problem_018_FindMaxValue {

	/**
	 * 返回单链表的最大值
	 * @时间复杂度 O(n)
	 * @param headNode
	 * @return
	 */
	public Integer findMax(SinglyNode<Integer> headNode){
		Integer max = null;
		
		if(headNode != null){
			max = headNode.getData();
		}
		
		//遍历链表
		while (headNode != null) {
			if(headNode.getData().intValue() > max.intValue()){
				max = headNode.getData();
			}
			headNode = headNode.getNext();
		}
		
		return max;
	}
	
	@Test
	public void testMethods(){
		SinglyNode<Integer> headNode = new SinglyNode<Integer>(1);		
		SinglyNode<Integer> tmpNode1 = new SinglyNode<Integer>(3);
		SinglyNode<Integer> tmpNode2 = new SinglyNode<Integer>(5);
		SinglyNode<Integer> tmpNode3 = new SinglyNode<Integer>(6);
		SinglyNode<Integer> tmpNode4 = new SinglyNode<Integer>(4);
		SinglyNode<Integer> tmpNode5 = new SinglyNode<Integer>(2);
		
		
		headNode.setNext(tmpNode1);
		tmpNode1.setNext(tmpNode2);
		tmpNode2.setNext(tmpNode3);
		tmpNode3.setNext(tmpNode4);
		tmpNode4.setNext(tmpNode5);
		
		System.out.println("链表的最大值是：" + findMax(headNode));
		
	}
	
}
